#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct DNode{
	int data;
	struct DNode *prior,*next;
	int length;
}DNode,*DLinkList;
DLinkList ListInit(){//链表的初始化。返回一个带有头结点的空链表
	DNode *head = (DNode*)malloc(sizeof(DNode));
	head->prior = NULL;
	head->next = NULL;
	head->length = 0;//只用头结点存储长度数据
	return head;
}
DLinkList ListCreate(DLinkList head){ //头插法创建初始链表
	int data;
	printf("请输入链表数据,-1结束输入:\n");
	while(scanf("%d",&data) != EOF && data != -1){
		DNode *newNode = (DNode*)malloc(sizeof(DNode));
		newNode->data = data;
		newNode->next = head->next;
		newNode->prior = head;
		if(head->next!=NULL){  //这里需要区分一下是空链表 因为head->next->prior
			head->next->prior = newNode;
		}
		head->next = newNode;
		head->length++;
	}
	return head;
}
DNode* GetNodeByValue(DLinkList head,int value){
	DNode *p = head->next;
	while(p){
		//假如值相同的话 .这里是只找第一个相同的值，只是最简单的模型
		if(p->data == value){//找到了就返回回去。
			return p;
		}
		p = p->next;
	}
	return NULL;//说明没找到
}
DNode* GetNodeByIndex(DLinkList head,int index){
	DNode *p = head->next;
	int i = 1;//这里的index是指我们正常理解中次序，而不是计算机的数组下标。所有index是从零开始
	while(p){
		if(i == index){
			return p;
		}
		p = p->next;
		i++;
	}
	return NULL;
}
bool NodeDelete(DLinkList head, DNode *aim){//删除某个节点。
	//这是一个双向链表，删除的时候不需要传入前驱节点就可以完成删除操作。
	//在单向链表中，c语言没有引用的概念，在删除的时候，需要传入前驱节点。但是c++在递归删除的时候可以使用引用直接传入目标节点完成删除操作。
	if(aim == NULL){
		printf("不存在该节点！\n");
		return false;
	}
	aim->prior->next = aim->next;
	if(aim->next != NULL) //假如要删除最后一个节点的话
	aim->next->prior = aim->prior;
	free(aim);
	head->length--;
	return true;
}
bool ListInsert(DLinkList head,int index,int data){//这里的插入是根据位置插入
	//由于双向链表很方便，我们可以直接调用查找次序函数来找到要插入节点的后一个节点
	DNode *newNode = (DNode*)malloc(sizeof(DNode));
	newNode->data = data;
	newNode->prior = NULL; //声明指针不使用时要置空，避免出现问题
	newNode->next = NULL;
	
	DNode *aimNext;
	//插入位置是尾部的话
	if(index == head->length+1 ){ //
		DNode *aimPrior = GetNodeByIndex(head,index-1); //此时我们找要插入的前驱节点
		newNode->next = NULL;
		newNode->prior = aimPrior;
		aimPrior->next = newNode;
		head->length++;
	}
	//插入位置不是尾部的话
	else {
		DNode * aimNext = GetNodeByIndex(head,index);
		newNode->next = aimNext;
		newNode->prior = aimNext->prior;
		aimNext->prior->next = newNode;
		aimNext->prior = newNode;
		head->length++;
		return true;
	}
	return false;
} 
void PrintList(DLinkList head){
	DNode *p = head->next;
	printf("链表长度为:%d\n",head->length);
	while(p){
		printf("%d ",p->data);
		p = p->next;
	}
}
int main(int argc, char *argv[]) {
	DLinkList list = ListInit();
	ListCreate(list);
	printf("链表为：\n");
	PrintList(list);
	printf("\n删除操作(0.按值删除 1.按次序删除\n");
	int choose,aim;
	scanf("%d",&choose);
	printf("请输入你要删除的值或次序:");
	scanf("%d",&aim);	
	if(choose == 0){
		NodeDelete(list,GetNodeByValue(list, aim));
	}
	else {
		NodeDelete(list,GetNodeByIndex(list, aim));
	}
	PrintList(list);
	printf("插入操作:\n");
	int index,data;
	printf("请输入数据：形如( 1 20 )在1位置插入20:\n");
	scanf("%d%d",&index,&data);
	ListInsert(list, index, data);
	PrintList(list);
}